package com.hr.尚学堂.线性表;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author zhz
 * @date 2020/10/03
 **/
public class 找数组中重复的元素 {
    /**
     * 问题：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，
     * 但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     * 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2
     *
     * 解决：第一种，用map做计数器，当大于1时，则返回true，否则false
     */
    public static boolean duplicate(int numbers[],int length,int [] duplication) {
        Map<Integer, Integer> map = new HashMap<>();
        int count=1;
        // 1.判断arr为null或arr.length等于0的情况
        if(numbers == null || length == 0) {
            return false;
        }
        for (int i = 0; i < length; i++) {
            // 3.判断数组元素是否合法
            if(numbers[i] < 0) {
                return false;
            }
            if (!map.containsKey(numbers[i])){
                map.put(numbers[i],count);
            }else{
                map.put(numbers[i],map.get(numbers[i])+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry : map.entrySet()){
            if (entry.getValue()>1){
                duplication[0]=entry.getKey();
                return true;
            }
        }
        return false;
    }

    /**
     * 题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数
     * 组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
     * 请找出数组中任意一个重复的数字。
     *
     * 解决：用set去判重
     */
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set=new HashSet<>();;
        int res=0;
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
            }else {
                res=num;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        找数组中重复的元素.duplicate(new int[]{
                0, 3, 4, 1, 4, 8
        },6,new int[]{1});
    }
}
